import numpy as np
from math import sqrt
from collections import Counter


def kNN_classify(k, X_trian, y_trian, x):

    assert 1 <= k <= X_trian.shape[0]
    assert X_trian.shape[0] == y_trian.shape[0]
    assert X_trian.shape[1] == x.shape[0]

    distances = [sqrt(np.sum((x_trian - x)**2)) for x_trian in X_trian]
    nearest = np.argsort(distances)

    topK_y = [y_trian[i] for i in nearest[:k]]
    votes = Counter(topK_y)

    return votes.most_common(1)[0][0]
